package io.zouyalong.algo.leetcode;

import java.util.HashMap;
import java.util.Map;

/**
 * 最长回文子串
 * https://leetcode-cn.com/problems/longest-palindromic-substring/
 * <p>
 * <p>
 * 可参考解法 https://leetcode-cn.com/problems/longest-palindromic-substring/solution/zhong-xin-kuo-san-dong-tai-gui-hua-by-liweiwei1419/
 */

class record {
    boolean isPalindromic;

    public record(boolean val) {
        this.isPalindromic = val;
    }
}

public class LongestPalindromicSubstring {

    public static void main(String[] args) {
        var src = "abacab";
        var inst = new LongestPalindromicSubstring();
        System.out.printf("result: %s\n", inst.solution1dp(src));
        System.out.printf("result2: %s\n", inst.solution2dp(src));
    }

    private boolean isPalindromic(char[] src, int left, int right) {
        for (; left < right; left++, right--) {
            if (src[left] != src[right]) {
                return false;
            }
        }
        return true;
    }

    private boolean isPalindromic(char[] src, int left, int right, record[][] memo) {
        if (memo[left][right] != null) {
            return memo[left][right].isPalindromic;
        }
        if (left > right) {
            return false;
        }
        boolean palindromic = false;
        if (left == right) {
            palindromic = true;
        } else if (left == right - 1) {
            palindromic = src[left] == src[right];
        } else {
            palindromic = src[left] == src[right] && isPalindromic(src, left + 1, right - 1, memo);
        }
        memo[left][right] = new record(palindromic);
        return palindromic;
    }

    public String solution2dp(String s) {
        var n = s.length();
        if (n == 0 || n == 1) {
            return s;
        }
        var chars = s.toCharArray();
        var memo = new boolean[n][n];
        for (int i = 0; i < n; i++) {
            memo[i][i] = true;
        }
        var maxLen = 1;
        String maxStr = s.substring(0, 1);
        for (int left = n - 2; left >= 0; left--) {
            for (int right = left + 1; right < n; right++) {
                var val = false;
                if (left == right-1) {
                    val = chars[left] == chars[right];
                } else {
                    val = chars[left] == chars[right] && memo[left+1][right-1];
                }
                if (val && right - left + 1 > maxLen) {
                    maxStr = s.substring(left, right + 1);
                }
                memo[left][right] = val;
            }
        }
        return maxStr;
    }

    public String solution1dp(String s) {
        if (s == null || s.length() == 0) {
            return "";
        }
        var longestStrStart = 0;
        var longestStrLen = 1;
        var suffixStart = 0;
        var chars = s.toCharArray();
        for (int i = 1; i < chars.length; i++) {
            if (suffixStart > 0 && chars[suffixStart - 1] == chars[i]) {
                suffixStart = suffixStart - 1;
            } else {
                for (int j = suffixStart; j <= i; j++) {
                    if (isPalindromic(chars, j, i)) {
                        suffixStart = j;
                        break;
                    }
                }
            }
            var currentSuffixLen = i - suffixStart + 1;
            if (currentSuffixLen > longestStrLen) {
                longestStrLen = currentSuffixLen;
                longestStrStart = suffixStart;
            }
        }
        return s.substring(longestStrStart, longestStrStart + longestStrLen);
    }
}
